1216. Valid Palindrome III
Hard

Given a string s and an integer k, return true if s is a k-palindrome.

A string is k-palindrome if it can be transformed into a palindrome by removing at most k characters from it.

 

Example 1:

Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.

Example 2:

Input: s = "abbababa", k = 1
Output: true

 

Constraints:

  • 1 <= s.length <= 1000
  • s consists of only lowercase English letters.
  • 1 <= k <= s.length
Accepted
16.3K
Submissions
32.4K
Seen this question in a real interview before?
Companies
Show Hint 1
Can you reduce this problem to a classic problem?
Show Hint 2
The problem is equivalent to finding any palindromic subsequence of length at least N-K where N is the length of the string.
Show Hint 3
Try to find the longest palindromic subsequence.
Show Hint 4
Use DP to do that.

Average Rating: 5.00 (10 votes)

Premium

Solution


Approach 1: Top-Down DP (2D)

Intuition

Let's try to find the minimum number of character that can be removed to make the string a palindrome. If we see that the minimum number is less than or equal to k we can conclude that it is indeed a K-Palindrome, else it is not.

Similar Problems:

Algorithm

How do we find the minimum characters to be removed to make it a palindrome? Let's imagine matching the characters of the string like a palindrome, from the beginning and the end with 2 pointers i and j. We may encounter the following two scenarios:

  1. The character at i matches character at j.
  2. The characters don't match each other.

For case 1 we just increase the pointer i and decrease the pointer j, i++ and j-- respectively.

In the second case we have 2 options:

  • Remove character at j and see if the previous character matches character at i.

Or

  • Remove character at i and see if the next character matches character at j.

Since we are not actually removing the characters from the string but just calculating the number of characters to be removed, in case 1 we decrement the pointer j by 1 and i stays as it is, as we still need a character to match character at i and in case 2 we increment the pointer i by 1 and j stays as it is, as we still need a character to match character at j. In both the cases we remove 1 character and thus it adds 1 to the cost.

We can then use these two different pairs of new i and j values (i+1, j and i, j-1) to again repeat the process and get the minimum result of them as our result for current pair i, j.

We can see that this is recursive and thus we can use recursion with caching to store the repeated values.

Complexity Analysis

  • Time complexity : O(n2)O(n^2). Where n is the length of string s. This is due to the fact that we try to find result for all combinations of i and j where i and j range from 0 to n, to compute a combination we perform an O(1)O(1) operation thus the final complexity is O(n2)O(n^2).

  • Space complexity : O(n2)O(n^2). Where n is the length of string s. This is due to caching all the results in memo table. The recursion stack depth can reach at max O(n)O(n) depth. Thus the complexity is dominated by the space required for memo.



Approach 2: Bottom-Up DP (2D)

Algorithm

Instead of filing up our memo table from top to bottom, let's try filling it from bottom to top. All we need to do is fill all the combinations of i and j in the correct order so that we have all the results required for the next state (combination of i, j) before we move to the next state (combination of i, j).

Complexity Analysis

  • Time complexity : O(n2)O(n^2). Where n is the length of string s. This is due to the fact that we try to find result for all combinations of i and j where i and j range from 0 to n, to compute a combination we perform an O(1)O(1) operation thus the final complexity is O(n2)O(n^2).

  • Space complexity : O(n2)O(n^2). Where n is the length of string s. This is due to the memo table which is completely filled in this case.



Approach 3: Bottom-Up DP (1D)

Algorithm

On looking closely to both the approaches mentioned above you'll notice that for any combination of i and j, you essentially only need the i+1'th row and j-1'th column. Thus we know we can reduce the space complexity to only O(n)O(n) from O(n2)O(n^2).

An efficient way of doing so is using the previous contained value in the memo which represents result for the previous state before storing the result for current state. This is better than the approach of managing two arrays (previous and current) and copying them after every calculation.

Complexity Analysis

  • Time complexity : O(n2)O(n^2). Where n is the length of string s. This is due to the fact that we try to find result for all combinations of i and j where i and j range from 0 to n, to compute a combination we perform an O(1)O(1) operation thus the final complexity is O(n2)O(n^2).

  • Space complexity : O(n)O(n). Where n is the length of string s. This is due to the memo table which stores result for only one row/i and all it's combination columns/j.


Report Article Issue

Comments: 2
scboy's avatar
Read More

very clear,thank you. I think it is one of the best solution in leetcode.

2
Reply
Share
Report
ltbtb_rise's avatar
Read More

brilliant solution. thank you!

what is the thinking process/mindset/intuition of working out the correct order for combinations of (i, j) ? I was quite struggling on that.

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium